package leetcode.day_2021_03_8_2021_03_14;

import sun.plugin.javascript.navig.LinkArray;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * https://leetcode-cn.com/problems/spiral-matrix/
 */
public class LeetCode0054 {

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        boolean[][] visted = new boolean[matrix.length][matrix[0].length];
        dfs(matrix, visted, 0, 0, list);
        return list;
    }

    public static void dfs(int[][] matrix, boolean[][] visited, int i, int j, List<Integer> list) {
        if (i<0 || j<0 || i>=visited.length || j>=visited[0].length || visited[i][j]) return;

        list.add(matrix[i][j]);
        visited[i][j] = true;
        // 目的是为了防止从下往上时会进入向右的递归
        if(j-1<0 || visited[i][j-1]==true){
            dfs (matrix, visited, i-1, j, list);
        }
        // 右，下，左，上
        dfs(matrix, visited, i, j+1, list);
        dfs(matrix, visited, i+1, j, list);
        dfs(matrix, visited, i, j-1, list);
        dfs(matrix, visited, i-1, j, list);
    }

    public static void main(String[] args) {
        int[][] arr = {
                {1,2,3, 4},
                {5,6,7,8},
                {9,10,11,12},
                {13, 14,15,16}

        };
        List<Integer> list = spiralOrder(arr);
        System.out.println(list);
    }
}
